/**
 * FileName: answer_1
 * Author:   why
 * Date:     2019/3/13 11:39
 * Description:
 */
package algorithm.leetcode.problem_509;


import java.util.Arrays;

public class answer_2 {
    public int fib(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 0);
        return add(dp, n);
    }

    public int add(int[] dp, int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        if (dp[n] != 0) {
            return dp[n];
        }
        dp[n] = add(dp, n - 1) + add(dp, n - 2);
        return dp[n];
    }
}
